package cn.huawei;

import sun.reflect.generics.tree.Tree;

import java.util.*;

/*
@李子宁
Happy,happy everyday!
冲鸭！
2020/8/16

*/
public class solution {

    public ArrayList<String> list=new ArrayList<>();
    public static void main(String[] args) {
       solution solution = new solution();
       /*
        ListNode A = new ListNode(3);
        ListNode B = new ListNode(2);
        ListNode C = new ListNode(4);
        ListNode D = new ListNode(6);
        ListNode E = new ListNode(8);
        ListNode F = new ListNode(1);

        A.next = B;
        B.next = C;
        C.next = D;
        D.next = E;
        E.next = F;
        reorderList(A);
        while (A!=null){
            System.out.println(A.val+"-");
            A = A.next;
        }*/
       TreeNode A = new TreeNode(4);
       TreeNode B = new TreeNode(9);
       TreeNode C = new TreeNode(1);
       TreeNode D = new TreeNode(0);
        A.left = B;
       A.right = D;
       B.right = C;
        System.out.println(solution.sumNumbers(A));

    }

    public String s = "";
    public int sum = 0;
    public int sumNumbers(TreeNode root) {
        int sum = 0;
        if (root == null) {
            return sum;
        }
        return preorderSumNumbers(root, sum);
    }
    public int preorderSumNumbers(TreeNode root, int sum) {
        if (root == null)
            return 0;
        sum = sum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return sum;
        }
        return preorderSumNumbers(root.left, sum) + preorderSumNumbers(root.right, sum);
    }

    public int singleNumber (int[] A) {
        // write code here
        for (int i = 0; i < A.length; i++) {
            int j = i;

        }
        return 0;
    }


    public boolean wordBreak(String s, Set<String> wordDict) {
        int len = s.length();

        boolean[] flags = new boolean[len+1];
        flags[0] = true;

        for (int i = 1; i <= len; i++) {
            for (int j = 0; j < i; j++) {
                if (flags[j] == true && wordDict.contains(s.substring(j,i))) {
                    flags[i] = true;
                    break;
                }
            }
        }

        return flags[len];
    }
    public ListNode detectCycle(ListNode head) {
        ListNode p = head;
        ListNode q = head;
        boolean flag = false;
        while (p!=null && p.next !=null){
            q = q.next;
            p = p.next.next;

            if (p == q){
                flag = true;
                break;
            }
        }
        if (!flag){
            return null;
        }else{
            int n = 1;
            p = p.next;
            while (p!=q){
                p = p.next;
                n++;
            }
            p = q = head;
            for (int i = 0; i < n; i++) {
                p = p.next;
            }
            while (p!=q){
                p = p.next;
                q = q.next;
            }
            return q;
        }

    }
   /* public ArrayList<String> wordBreak(String s, Set<String> dict) {
        dfs(s,"",s.length(),dict);
        return list;
    }*/

    public void dfs(String s, String str, int index, Set<String> dict) {
        if(index <=0) {
            if (str.length()>0) {
                list.add(str.substring(0,str.length()-1));
            }
        }
        for(int i=index; i>=0; i--){
            String sub = s.substring(i,index);
            if(dict.contains(sub)) {
                String tmp = str;
                str = sub + " " + str;
                dfs(s, str, i, dict);
                str = tmp;
            }
        }
    }
    public ListNode insertionSortList (ListNode head) {
        ListNode result = new ListNode(-1);
        ListNode t = new ListNode(head.val);
        result.next = t;
        head = head.next;
        boolean flag = true;
        while(head!=null){
            ListNode before = result;
            ListNode cur = result.next;
            while (cur!=null && flag){
                if ( head!=null&&cur.val>head.val){
                    ListNode tmp = new ListNode(head.val);
                    before.next = null;
                    tmp.next = cur;
                    before.next = tmp;
                    head = head.next;
                    flag = false;
                    continue;
                }
                before = before.next;
                cur = cur.next;
            }
            if (flag){
               ListNode tmp = new ListNode(head.val);
               before.next = tmp;
                head = head.next;
            }
            flag = true;
        }
        return result.next;
    }
    public  static void reorderList(ListNode head) {
        ListNode tmp = head;
        Stack<ListNode> st = new Stack<>();
        int size = getLength(head);
        for (int i = 0; i < size/2; i++) {
            tmp = tmp.next;
        }
        while (tmp!=null){
            st.push(tmp);
            tmp = tmp.next;
        }
        ListNode result = head;
        ListNode cur = result.next;
        while (!st.isEmpty()){
            ListNode pop = st.pop();
            result.next = null;
            pop.next = cur;
            result.next = pop;
            result = cur;
            cur = cur.next;
        }
        cur.next = null;
    }
    public static int getLength(ListNode head){
        int count =0;
        while (head != null){
            count++;
            head = head.next;
        }
        return count;
    }


    public int evalRPN (String[] tokens) {
        // write code here
        String s = "+-*/";
        Stack stack = new Stack();
        for (int i = 0; i < tokens.length; i++) {
            if (s.contains(tokens[i])){
                int a = (int) stack.pop();
                int b = (int) stack.pop();
                int c = -1;
                switch (tokens[i]){
                    case "+": c = a + b;break;
                    case "-": c = b - a;break;
                    case "*": c = a*b;break;
                    case "/": c = b/a;break;
                }
                stack.add(c);
            }else{
                stack.add(Integer.parseInt(tokens[i]));
            }
        }
        return (int) stack.pop();
    }
/*********/
    public int maxPoints (Point[] points) {
        // write code here
        if (points.length == 0){
            return 0;
        }
        if (points.length == 1){
            return 1;
        }
        Map<String,Set<Point>> map = new HashMap<>();
        for (int i = 0; i < points.length-1; i++) {
            for (int j = i+1; j <points.length; j++) {
               String k = points[i].x == points[j].x ? k = "inf" :((double)(points[j].y - points[i].y))/(double)(points[j].x - points[i].x)+"";
               if (map.containsKey(k)){
                   Set<Point> set = map.get(k);
                   set.add(points[i]);
                   set.add(points[j]);
                   map.put(k,set);

               }else {
                   Set<Point> set = new HashSet<>();
                   set.add(points[i]);
                   set.add(points[j]);
                   map.put(k,set);
               }
            }
        }
        int max = 0;
        for (Set<Point> value : map.values()) {
            max = value.size()>= max ? value.size() : max;
        }
        return max;
    }

    public ListNode sortList (ListNode head) {
        // write code here
       sort(head);
       return head;
    }

    public void sort(ListNode head){
        int size = 0;
        ListNode tmp = head;
        while (tmp!=null){
            size++;
            tmp = tmp.next;
        }
        int mid = size / 2;
        ListNode node2 = head;
        ListNode node1 = head;
        while (mid-- >0){
            node2 = node2.next;
        }
        if (node1!=null && node2!=null){
            sort(node1);
            sort(node2);
            merge(node1, node2);
        }
    }

    public void merge(ListNode node1,ListNode node2){
        ListNode left = node1;
        ListNode right = node2;
        ListNode tmp = null;
        if (left.val <= right.val){
            tmp.next = left;
            left = left.next;
            tmp = tmp.next;
        }else{
            tmp.next = right;
            right = right.next;
            tmp = tmp.next;
        }
        while (left!=null && right!= null){
            if (left.val <= right.val){
                tmp.next = left;
                left = left.next;
                tmp = tmp.next;
            }else{
                tmp.next = right;
                right = right.next;
                tmp = tmp.next;
            }
        }
        while (left!=null){
            tmp.next = left;
            left = left.next;
            tmp = tmp.next;
        }
        while (right!=null){
            tmp.next = right;
            right = right.next;
            tmp = tmp.next;
        }

    }

}
class Point {
    int x;
    int y;

    Point(int x,int y){
        this.x = x;
        this.y = y;
    }

  }


class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val){
        this.val = val;
    }
  }

class TreeNode {

    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    TreeNode(int val){
        this.val = val;
    }
 }